package expr

import (
	"container/list"
	"fmt"
	"strconv"
)

// Expr : the expression structure.
type Expr interface {
	Compute() float64
	String() string
}

type valExpr float64

// Compute : compute the value of the expression.
func (e valExpr) Compute() float64 {
	return float64(e)
}

// String : get the string of the expression.
func (e valExpr) String() string {
	return fmt.Sprintf("%.6f", e)
}

type opType rune

func (a opType) Less(b opType) bool {
	if a == '+' || a == '-' {
		return b != '+' && b != '-'
	} else if a == '*' || a == '/' {
		return a == '(' || a == ')'
	} else {
		return false
	}
}

func (a opType) String() string {
	return fmt.Sprintf("%c", a)
}

type opExpr struct {
	op    opType
	left  Expr
	right Expr
}

func (e opExpr) Compute() float64 {
	switch e.op {
	case '+':
		return e.left.Compute() + e.right.Compute()
	case '-':
		return e.left.Compute() - e.right.Compute()
	case '*':
		return e.left.Compute() * e.right.Compute()
	case '/':
		return e.left.Compute() / e.right.Compute()
	default:
		return 0
	}
}

func (e opExpr) String() string {
	return "(" + e.left.String() + e.op.String() + e.right.String() + ")"
}

func parseToken(text string, ch chan<- string) {
	last := ' '
	currentToken := ""
	textLen := len(text)
	for i := 0; i < textLen; i++ {
		c := rune(text[textLen-1-i])
		switch c {
		case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
			if last >= '0' && last <= '9' {
				currentToken = string(c) + currentToken
				break
			} else if last == '-' {
				ch <- currentToken
				ch <- "-"
				currentToken = string(c)
				break
			}
			fallthrough
		case '+', '*', '/', '(', ')':
			if len(currentToken) > 0 {
				if last == '-' {
					ch <- "-" + currentToken
				} else {
					ch <- currentToken
				}
			}
			currentToken = string(c)
		case '-', ' ':
			// skip...
		default:
			close(ch)
			return
		}
		if c != ' ' {
			last = c
		}
	}
	if len(currentToken) > 0 {
		if last == '-' {
			ch <- "-" + currentToken
		} else {
			ch <- currentToken
		}
	}
	close(ch)
}

type opStack struct {
	internal *list.List
}

func (o *opStack) peek() opType {
	return o.internal.Front().Value.(opType)
}

func (o *opStack) push(op opType) {
	o.internal.PushFront(op)
}

func (o *opStack) pop() opType {
	op := o.internal.Front().Value.(opType)
	o.internal.Remove(o.internal.Front())
	return op
}

func (o *opStack) isEmpty() bool {
	return o.internal.Len() == 0
}

type exprStack struct {
	internal *list.List
}

func (e *exprStack) peek() Expr {
	return e.internal.Front().Value.(Expr)
}

func (e *exprStack) push(expr Expr) {
	e.internal.PushFront(expr)
}

func (e *exprStack) pop() Expr {
	expr := e.internal.Front().Value.(Expr)
	e.internal.Remove(e.internal.Front())
	return expr
}

func (e *exprStack) isEmpty() bool {
	return e.internal.Len() == 0
}

func parseExpr(ch <-chan string) (Expr, error) {
	es := exprStack{list.New()}
	os := opStack{list.New()}
	for token := range ch {
		// fmt.Println(token)
		switch token {
		case "(":
			for !os.isEmpty() && os.peek() != ')' {
				o := os.pop()
				left := es.pop()
				right := es.pop()
				es.push(opExpr{o, left, right})
			}
			if os.isEmpty() {
				return nil, fmt.Errorf("unexpected operator '(' is found")
			}
			os.pop()
		case ")", "+", "-", "*", "/":
			op := opType(token[0])
			for !os.isEmpty() && os.peek() != ')' && op.Less(os.peek()) {
				o := os.pop()
				left := es.pop()
				right := es.pop()
				es.push(opExpr{o, left, right})
			}
			os.push(op)
		default: // numeric
			n, _ := strconv.ParseFloat(token, 64)
			es.push(valExpr(n))
		}
	}
	for !os.isEmpty() {
		o := os.pop()
		left := es.pop()
		if es.isEmpty() {
			return nil, fmt.Errorf("no corresponding operand are found")
		}
		right := es.pop()
		es.push(opExpr{o, left, right})
	}
	return es.pop(), nil
}

// ParseExpr : parse the text into expression.
func ParseExpr(text string) (Expr, error) {
	ch := make(chan string)
	go parseToken(text, ch)
	return parseExpr(ch)
}
